package main

import (
	"fmt"
)

/*
给定一个按非递减顺序排序的整数数组 A，
返回每个数字的平方组成的新数组，要求也按非递减顺序排序。

示例 1：
输入：[-4,-1,0,3,10]
输出：[0,1,9,16,100]

*/

// 方法一： 暴力法
/*
func sortedSquares(nums []int) []int {
	for i, _ := range nums{
		if nums[i] < 0{
			nums[i] = -nums[i]
		}
	}
	sort.Ints(nums)
	var resNums []int
	for i, _ := range nums{
		resNums = append(resNums, nums[i]*nums[i])
	}
	return resNums
}
*/

//  方法二： 双指针
func sortedSquares(nums []int) []int {
	n := len(nums)
	resNums := make([]int, n)
	left, right := 0, n-1
	for i := n - 1; i >= 0; i-- {
		if v, m := nums[left]*nums[left], nums[right]*nums[right]; v > m {
			resNums[i] = v
			left++
		} else {
			resNums[i] = m
			right--
		}
	}
	return resNums
}

func main() {
	fmt.Println(sortedSquares([]int{-4, -1, 0, 3, 10}))
}
